package leetcode_901_1000;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeeCode_927 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(threeEqualParts(new int[]{1, 0, 1, 0, 1})));
        System.out.println(Arrays.toString(threeEqualParts(new int[]{1,1,0,1,1})));
        System.out.println(Arrays.toString(threeEqualParts(new int[]{1,1,0,0,1})));
    }
    private static int[] threeEqualParts(int[] arr) {
        int n = arr.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1){
                list.add(i);
            }
        }
        int m = list.size();
        if (m % 3 != 0)
            return new int[]{-1, -1};
        if (m == 0)
            return new int[]{0, 2};
        int av = m / 3;
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        StringBuilder s3 = new StringBuilder();
        Integer aftI = list.get(m - av);
        for (int i = n - 1; i >= aftI; i--){
            s1.append(arr[i]);
        }
        int len = s1.length();
        Integer preI = list.get(m - av * 2);
        if (preI + len - 1 >= aftI)
            return new int[]{-1, -1};
        for(int i = preI + len - 1; i >= preI; i--){
            s2.append(arr[i]);
        }
        for (int i = list.get(0) + len - 1;  i >= list.get(0); i--){
            s3.append(arr[i]);
        }
        return s1.toString().equals(s2.toString()) && s2.toString().equals(s3.toString()) ?
                new int[]{list.get(0) + len - 1, preI + len} : new int[]{-1, -1};
    }
}